import javax.xml.soap.Node;
import java.util.Stack;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: mac
 * Date: 2022-09-19
 * Time: 19:20
 */

//155.最小栈
class MinStack {

    private Stack<Integer> stack;
    private Stack<Integer> minstack;

    public MinStack() {
        stack = new Stack<>();
        minstack = new Stack<>();
    }

    public void push(int val) {
        stack.push((val));
        if (!minstack.empty()){
            int top = minstack.peek();
            if (top >= val){
                minstack.push(val);
            }
        }else{
            minstack.push(val);
        }
    }

    public void pop() {
        int popVal = stack.pop();
        if (!minstack.empty()){
            if (popVal == minstack.peek()){
                minstack.pop();
            }
        }
    }

    public int top() {
        return stack.peek();
    }

    public int getMin() {
        return minstack.peek();
    }
}
public class Day2 {
    //20.有效的括号 - 标记
    public boolean isValid1(String s) {
        Stack<Character> stack = new Stack<>();
        for (char c:s.toCharArray()
             ) {
            if (c == '(') stack.push(')');
            else if (c == '[') stack.push(']');
            else if (c == '{') stack.push('}');
            else if (stack.empty() || c != stack.pop()) return false;
        }
        return stack.empty();
    }
    public boolean isValid2(String s) {
        Stack<Character> stack = new Stack<>();

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(') stack.push('(');
            else if(c == '[') stack.push('[');
            else if (c == '{') stack.push('{');
            else if (stack.empty()) {
                char d = stack.peek();
                if (c == ')' && d == '(' || c == ']' && d == '[' || c == '}' && d == '{'){
                    stack.pop();
                }else{
                    break;
                }
            }else{
                return false;
            }
        }
        return stack.empty();
    }
}
